package leetcode;

import java.util.Arrays;

public class LC7 {
    public static void main(String[] args) {
        LC7 lc7 = new LC7();
        System.out.println(lc7.trap1(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    public int trap1(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        System.out.println(Arrays.toString(leftMax));
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        System.out.println(Arrays.toString(rightMax));
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
    public int trap(int[] height) {
        int max = 0;
        int maxIndex = 0;
        for(int i = 0; i< height.length; i++){
            if(height[i] > max){
                max = height[i];
                maxIndex = i;
            }
        }
        int wa = 0;
        int left = height[0];
        int right = height[height.length-1];
        for(int i = 1; i<maxIndex; i++){
            if(height[i] < left){
                wa += left-height[i];
            }else{
                left = height[i];
            }
        }
        for (int i = height.length-2; i > maxIndex ; i--) {
            if(height[i]<right){
                wa += right - height[i];
            }else{
                right = height[i];
            }
        }
        return wa;
    }
}
